|
|
Knihovna pro binární rozhodovací diagramy
Janků, Petr ; Hrubý, Martin (oponent) ; Holík, Lukáš (vedoucí práce)
Efektivní manipulace Booleovských funkcí je důležitou součástí mnoha počítačových návrhů. Jako datová struktura pro reprezentaci a manipulaci s Booleovskými funkcemi se běžně používají binární rozhodovací diagramy. Tyto diagramy se běžně používají v mnoha odvětvích, jako je například ověřování modelů, verifikace systému, návrh obvodů apod. V této práci jsou popsány tyto diagramy a jsou zde uvedeny i jejich modifikace. Dále jsou v této práci uvedeny a popsány techniky pro efektivní manipulaci a reprezentaci binárních rozhodovacích diagramů. Mimoto tato práce popisuje návrh a implementaci knihovny, která bude s těmito diagramy pracovat. Dále je diskutována potenciální aplikace vyvinuté knihovny v knihovně VATA pro manipulaci se stromovými automaty. Na závěr je tato knihovna porovnána s dobře známou a silně optimalizovanou knihovnou CUDD, která je volně dostupná a s knihovnou CacBDD. Výsledky experimentů ukázaly, že navrhovaná knihovna je poměrně blízká CUDD a CacBDD (dosahuje srovnatelného a většinou i lehce lepšího výkonu).
|
|
| |
|
|
A Library for Binary Decision Diagrams
Paulovčák, Martin ; Holík, Lukáš (oponent) ; Lengál, Ondřej (vedoucí práce)
The aim of this thesis is to create an easy-to-use library that will provide the basic means for Boolean function manipulation based on six different variants of Binary Decision Diagrams - BDD, ZDD, CBDD, CZDD, TBDD, and ESRBDD. The library is implemented in the ISO C programming language, uses closed hashing, index-based node referencing, mark and sweep based garbage collector and diagram construction is based on classical depth-first traversal. The implemented variants of these diagrams were compared on benchmarks and although the optimal choice of decision diagram variant depends on given problem, in general TBDD proved to be the best choice in terms of the resulting graph size and also CPU time.
|
|
|
Vlastnosti intervalových booleovských funkcí
Hušek, Radek ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
Tato práce řeší problém rozpoznávání k-intervalových boolovských funkcí. Na vstup bo- olovské funkce můžeme nahlížet jako na binární zápis přirozeného čísla. Funkce je k- intervalová, pokud - při takto interpretovaném vstupu - nabývá hodnoty jedna právě pro vstupy z daných nejvýše k intervalů. Tento problém je pro obecné boolovské funkce zadané DNF coNP-těžký. Proto se zabýváme případem, kdy DNF náleží do dané řešitelné třídy (třída je řešitelná, pokud pro DNF z ní umíme řešit falsifikovatelnost v polynomiál- ním čase a je uzavřená na částečná dosazení), a ukazujeme, že v tomto případě je úloha pro pevné k řešitelná v polynomiálním čase. 1
|
|
|
Boolean methods in knowledge compilation
Kaleyski, Nikolay Stoyanov ; Čepek, Ondřej (vedoucí práce) ; Gregor, Petr (oponent)
V rámci práce je vyřešen otevřený problém o relativní úspornosti jazyků PI a MODS. Ukazuje se, že PI není alespoň tak úsporný jako MODS tím, že se konstruuje třída Booleovských funkcí s počtem primárních implikantů který je superpolynomiální vzhledem k počtu nulových bodů zkonstruovaných funkcí. Odvozuje se dolní mez (čím se dokazuje, že PI není alespoň tak úsporný jako MODS), horní mez (která ukazuje, že zkonstruovaný protipříklad nemůže poskytnout exponenciální separaci PI a MODS) a vzorec pro přesný počet primárních implikantů zkonstruovaných funkcí. Powered by TCPDF (www.tcpdf.org)
|
|
|
Vlastnosti intervalových booleovských funkcí
Hušek, Radek ; Čepek, Ondřej (vedoucí práce)
Tato práce řeší problém rozpoznávání k-intervalových boolovských funkcí. Na vstup bo- olovské funkce můžeme nahlížet jako na binární zápis přirozeného čísla. Funkce je k- intervalová, pokud - při takto interpretovaném vstupu - nabývá hodnoty jedna právě pro vstupy z daných nejvýše k intervalů. Tento problém je pro obecné boolovské funkce zadané DNF coNP-těžký. Proto se zabýváme případem, kdy DNF náleží do dané řešitelné třídy (třída je řešitelná, pokud pro DNF z ní umíme řešit falsifikovatelnost v polynomiál- ním čase a je uzavřená na částečná dosazení), a ukazujeme, že v tomto případě je úloha pro pevné k řešitelná v polynomiálním čase. 1
|
|
|
Boolean techniques in Knowledge representation
Chromý, Miloš ; Čepek, Ondřej (vedoucí práce)
Název: Booleovské techniky v Reprezentaci znalostí Autor: Miloš Chromý Katedra: Katedra teoretické matematiky a matematické logiky Vedoucí práce: Doc. RNDr. Ondřej Čepek, Ph.D., Katedra teoretické matem- atiky a matematické logiky Abstrakt: V této práci zkoumáme switch-list reprezentace Booleovských funkcí a biklikově splnitelné formule. Reprezentace booleovské funkce f pomocí switch-listu je tvořena seznamem ohod- nocení z pravdivostní tabulky, jejichž funkční hodnota se liší od hodnoty před- cházející, tedy f(x) ̸= f(x − 1). V této práci se zaměříme na zahrnutí tohoto typu reprezentace do mapy kompilace znalostí (Knowledge Compilation Map, [Darwiche and Marquis, 2002]). Ukážeme, že switch-list reprezentace může být vhodným cílovým jazykem pro kompilaci znalostí. Nejprve provedeme srovnání relativní velikosti switch-list reprezentace s některými zavedenými reprezentacemi booleovských funkcí (například CNF, DNF nebo OBDD). Součástí této analýzy je i odpověď na dlouho otevřenou otázku položenou v [Darwiche and Marquis, 2002] ohledně neporovnatelnosti jazyků MODS (seznam modelů) a PI (seznam primárních implikátů). Popíšeme také polynomiální algoritmus, který kompiluje switch-list reprezentaci do OBDD. Nakonec se budeme věnovat tomu, které z dotazů a transformací uvažovaných v knowledge compilation map...
|
|
|
Boolean techniques in Knowledge representation
Chromý, Miloš ; Čepek, Ondřej (vedoucí práce)
Název: Booleovské techniky v Reprezentaci znalostí Autor: Miloš Chromý Katedra: Katedra teoretické matematiky a matematické logiky Vedoucí práce: Doc. RNDr. Ondřej Čepek, Ph.D., Katedra teoretické matem- atiky a matematické logiky Abstrakt: V této práci zkoumáme switch-list reprezentace Booleovských funkcí a biklikově splnitelné formule. Reprezentace booleovské funkce f pomocí switch-listu je tvořena seznamem ohod- nocení z pravdivostní tabulky, jejichž funkční hodnota se liší od hodnoty před- cházející, tedy f(x) ̸= f(x − 1). V této práci se zaměříme na zahrnutí tohoto typu reprezentace do mapy kompilace znalostí (Knowledge Compilation Map, [Darwiche and Marquis, 2002]). Ukážeme, že switch-list reprezentace může být vhodným cílovým jazykem pro kompilaci znalostí. Nejprve provedeme srovnání relativní velikosti switch-list reprezentace s některými zavedenými reprezentacemi booleovských funkcí (například CNF, DNF nebo OBDD). Součástí této analýzy je i odpověď na dlouho otevřenou otázku položenou v [Darwiche and Marquis, 2002] ohledně neporovnatelnosti jazyků MODS (seznam modelů) a PI (seznam primárních implikátů). Popíšeme také polynomiální algoritmus, který kompiluje switch-list reprezentaci do OBDD. Nakonec se budeme věnovat tomu, které z dotazů a transformací uvažovaných v knowledge compilation map...
|
|
|
Boolean techniques in Knowledge representation
Chromý, Miloš ; Čepek, Ondřej (vedoucí práce) ; Mengel, Stefan (oponent) ; Kofroň, Jan (oponent)
Název: Booleovské techniky v Reprezentaci znalostí Autor: Miloš Chromý Katedra: Katedra teoretické matematiky a matematické logiky Vedoucí práce: Doc. RNDr. Ondřej Čepek, Ph.D., Katedra teoretické matem- atiky a matematické logiky Abstrakt: V této práci zkoumáme switch-list reprezentace Booleovských funkcí a biklikově splnitelné formule. Reprezentace booleovské funkce f pomocí switch-listu je tvořena seznamem ohod- nocení z pravdivostní tabulky, jejichž funkční hodnota se liší od hodnoty před- cházející, tedy f(x) ̸= f(x − 1). V této práci se zaměříme na zahrnutí tohoto typu reprezentace do mapy kompilace znalostí (Knowledge Compilation Map, [Darwiche and Marquis, 2002]). Ukážeme, že switch-list reprezentace může být vhodným cílovým jazykem pro kompilaci znalostí. Nejprve provedeme srovnání relativní velikosti switch-list reprezentace s některými zavedenými reprezentacemi booleovských funkcí (například CNF, DNF nebo OBDD). Součástí této analýzy je i odpověď na dlouho otevřenou otázku položenou v [Darwiche and Marquis, 2002] ohledně neporovnatelnosti jazyků MODS (seznam modelů) a PI (seznam primárních implikátů). Popíšeme také polynomiální algoritmus, který kompiluje switch-list reprezentaci do OBDD. Nakonec se budeme věnovat tomu, které z dotazů a transformací uvažovaných v knowledge compilation map...
|
|
|
Logic circuits as models of computation
Naumenko, Mykhailo ; Kazda, Alexandr (vedoucí práce) ; Kompatscher, Michael (oponent)
Tato práce se zaměřuje na studium logických obvodů. Vykládáme v ní teorii logických obvodů podle učebnice "Models of Computation" od Johna E. Savage a řešíme některé úlohy a cvičení z této učebnice. V této práci najdete klíčové pojmy související s logickými obvody. Věnovali jsme znač- nou pozornost hlavně odhadům dolních mezí velikostí obvodů a velikostí formulí obecných booleovských funkcí. Sestrojili jsme také několik jednoduchých příkladů známých obvodů a ukázali jsme, jak lze navrhnout další obvody. 1
|
host ::
RSS.